/**
 * @author 雷明浩
 * @date 2025/7/4 17:58
 */
public class Fibonacci {
    // 斐波拉契数列
    // https://www.nowcoder.com/practice/c6c7742f5ba7442aada113136ddea0c3?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3DSQL%25E7%25AF%2587%26topicId%3D295
    public int Fibonacci (int n) {
        // write code here
        int[] dp = new int[n];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i < n; i++) {
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n-1];
    }

    /**
     * 空间优化
     * @param n
     * @return
     */
    public int Fibonacci1 (int n) {
        // write code here
        int num1 = 1;
        int num2 = 1;
        for (int i = 2; i < n; i++) {
            int tmp = num1 + num2;
            num1 = num2;
            num2 = tmp;
        }
        return num2;
    }
}